#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<long long, long long> _hash;

int integerReplacement(int n) {
    return dfs(n);
}

int dfs(long long n)
{
    if (_hash.count(n))
    {
        return _hash[n];
    }

    if (n == 1)
    {
        _hash[1] = 0;
        return 0;
    }

    if (n % 2 == 0)
    {
        _hash[n] = dfs(n / 2) + 1;
        return _hash[n];
    }
    else
    {
        _hash[n] = min(dfs(n - 1), dfs(n + 1)) + 1;
        return _hash[n];
    }
}

int main()
{

	return 0;
}